package utils;

import java.util.LinkedList;
import java.util.Queue;

public class binaryTreeUtil {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }
     public static TreeNode buildTree(Integer[] array) {
        // 1. 处理边缘情况
        if (array == null || array.length == 0 || array[0] == null) {
            return null;
        }

        // 2. 创建根节点，并初始化队列
        TreeNode root = new TreeNode(array[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1; // 数组索引，从根节点的下一个元素开始

        // 3. 层序遍历构建树
        while (!queue.isEmpty() && i < array.length) {
            TreeNode currentNode = queue.poll(); // 取出父节点

            // 4. 构建左子节点
            if (i < array.length && array[i] != null) {
                TreeNode leftNode = new TreeNode(array[i]);
                currentNode.left = leftNode;
                queue.offer(leftNode); // 将左子节点入队
            }
            i++; // 数组索引向后移动一位

            // 5. 构建右子节点
            if (i < array.length && array[i] != null) {
                TreeNode rightNode = new TreeNode(array[i]);
                currentNode.right = rightNode;
                queue.offer(rightNode); // 将右子节点入队
            }
            i++; // 数组索引再向后移动一位
        }

        return root;
    }

    /**
     * (辅助方法) 层序遍历打印树，用于验证结果
     * @param root 树的根节点
     */
    public static void printTree(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        System.out.print("[");
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        System.out.println("]");
    }
}